The present invention relates to a method and its device for identifying the characteristics of an unknown system such as a transmission line, an acoustic coupling path and the like.
As applications of an unknown system identification performed by an adaptive filter, an echo canceler, a noise canceler, a howling canceler, an adaptive equalizer and the like are known. Here, taking an acoustic echo canceler which removes an acoustic echo leaking from a speaker into a microphone in the acoustic coupling path as an example, the prior art will be described below.
An echo canceler operates so as to suppress an acoustic echo leaking from a speaker into a microphone in the acoustic coupling path by generating an echo replica corresponding to a sending signal using an adaptive filter having a large number of tap coefficients more than that of an impulse response of the echo path. At this time, each tap coefficient of the adaptive filter is modified by correlating the error signal obtained by subtracting the echo replica from the mixed signal which is a compination of echo and the near-end signal, and far end signals.
As typical coefficient adaptation algorithms of these adaptive filters, xe2x80x98LMS algorithmxe2x80x99 in xe2x80x9cPROCEEDINGS OF IEEExe2x80x9d, Vol. 63, No. 12, pp. 1692-1716, December, 1975 (reference 1) and xe2x80x98Learning Identification Method, LIMxe2x80x99 in xe2x80x9cIEEE TRANSACTIONS ON AUTOMATIC CONTROLxe2x80x9d, Vol. 12, No. 3, pp. 282-287, March, 1967(reference 2) are known.
The impulse response length of an acoustic coupling where an acoustic echo canceler is actually used depends upon a physical size of the acoustic space, a reflection factor of the wall or the like. For example, assuming a room used for videoconference and the like, the impulse response length may reach 1,000 taps, or occasionally several thousands taps. Therefore, it often difficulty in realizing it from the viewpoint of calculation amount or hardware size.
Thus, mainly for solving the problem of a calculation amount increase, subband adaptive filters in which input signals are divided into subbands and each subband uses an adaptive filter have been proposed in xe2x80x9cIEEE SIGNAL PROCESSING MAGAZINExe2x80x9d, PP. 14-37, January, 1992 (reference 3).
As for the adaptive filter structure in each subband, various forms can be taken, but most common one is called an FIR (Finite Impulse Response)-type, and there is a reference made in xe2x80x9cIEEE TRANSACTIONS ON ACOUSTICS, SPEECH AND SIGNAL PROCESSINGxe2x80x9d, Vol. 27, No. 6, pp. 768-781, June, 1979 (reference 4).
The number N of taps of an adaptive FIR filter corresponding to each subband must be equal to the corresponding impulse response length, or longer than that. Commonly, in the case where an acoustic echo is divided into subbands, an impulse response in lower subbands is longer than that in higher subbands. This is mainly because an impulse response length of an acoustic coupling is determined by reflection, the reflection factor in a higher subband is smaller and higher subband components are more likely to be attenuated.
In FIG. 16, a typical impulse response of each subband in the case where an acoustic echo is divided into four (4) subbands is shown. Assuming that an impulse response length corresponding to the subband 1 through the subband 4 is M1,M2,M3, and M4, respectively, the impulse response lengths M1,M2,M3, and M4 are given by an inequality M1xe2x89xa7M2xe2x89xa7M3xe2x89xa7M4. A subband adaptive filter which can reduce the calculation amount and shorten the convergence time by considering these characteristics and by adaptively assigning the number of taps of an adaptive filter of each subband has been proposed in xe2x80x9cIEEE PROCEEDINGS OF INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING, Vol. V, pp. 3051-3053, April, 1995xe2x80x9d (reference 5).
In FIG. 17, a block diagram of a subband adaptive filter which has been described in xe2x80x98reference 5xe2x80x99 is shown. The number of taps of an adaptive filter is adaptively assigned by evaluating a coefficient values and information of the subband input signal obtained from each adaptive filter.
According to the method of xe2x80x98reference 5xe2x80x99 shown in FIG. 17, at first, input signals are divided into a plurality of subbands in the analysis filter bank 3 and subband input signals are generated. Each subband input signal is decimated by a factor of 1/Li in the decimating circuit 50i(i=1,2, . . . , K), and is supplied to an independent adaptive filter 60i(i=1,2, . . . , K), respectively, and usually, where Li is K. On the other hand, the output of an unknown system 2 which is to be identified, that is to say, the echo to be cancelled the echo canceler is decimated by w /a factor of 1/Li in the decimating circuit 51i(i=1,2, . . . , K) after becoming a subband echo divided into a plurality of subbands in another analysis filter bank 4 having the entirely the same characteristics with the analysis filter bank 3.
In an adaptive filter 60i, the subband error signal that is the difference between the subband replica which is the output of the adaptive filter and the subband echo which is decimated is generated. An adaptive filter 60i performs a coefficient adaptation using this subband error signal. This subband error signal is supplied to the synthesis filter bank 8 after it is interpolated w/a factor of Li in an interpolation circuit 70i(i=1,2, . . . , K), and transported to the output terminal 9 after it is synthesized into the full band.
Specifically, the signal obtained at the output terminal 9 be comes an echo-cancelled signal in the full band if each subband error signal is sufficiently small, that is to say, if the echo is sufficiently cancelled in each subband.
The tap assignment control circuit 10 receives a coefficient value 100 from adaptive filters 60i(i=1,2, . . . , K) of each subband, the number of taps 101 at a time (mxe2x88x921)UT and a subband input signal 102, calculates a signal 103 representing the number of taps of each subband, and transports it to an adaptive filter 60i of each subband. Here, T is a sampling period.
In FIG. 18, an example of the tap assignment control circuit 10 is shown. A coefficient value 100 is supplied from adaptive filters 60i(i=1,2, . . . , K) of each subband to the coefficient square value evaluation circuit 110. Assuming the coefficient vector Ci,k of the adaptive filter 60i at a time kT, each of coefficients Cij,k (j=1,2, . . . , N) is determined by
xe2x80x83ci,k=[ci,1,kci,2,k . . . ci,N,k]Txe2x80x83xe2x80x83(1)
where [.]T denotes vector transpos of [.].
In the coefficient square value evaluation circuit 110, the following value,
{overscore (c)}i,k=[ci,Nixe2x88x92P+1,kci,Nixe2x88x92P+2,k . . . ci,Ni,k]Txe2x80x83xe2x80x83(2)
is first calculated corresponding to each subband. Here, P is a positive integer, Ni,k is the number of taps of an adaptive filter of the i-th subband at time kT. That is to say, coefficients from the tail P tap portion is utilized for the evaluation in each subband. Moreover, the coefficient square value evaluation circuit 110 calculates as follows,                                           c            ~                    k                =                  [                                                    c                _                                            1                ,                k                            T                        ⁢                                                                                xe2x80x83                                    ⁢                  c                                _                                            1                ,                k                                      ⁢                                                                                xe2x80x83                                    ⁢                  c                                _                                            2                ,                k                            T                        ⁢                          xe2x80x83                        ⁢                                          c                _                                            2                ,                k                                      ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                                          c                _                                            K                ,                k                            T                        ⁢                          xe2x80x83                        ⁢                                          c                _                                            K                ,                k                                              ]                                    (        3        )            
where the result is transported to the calculation circuit of number of taps 130 as a tsubband tail coefficient vector 111. The input signal 102 of each adaptive filter in addition to an output 111 of the coefficient square value evaluation circuit 110 is supplied to the.
Now, the input signal power vector Vk at time kT are determined by                               V          k                =                              (                          [                                                χ                                      1                    ,                    k                                    2                                ⁢                                  xe2x80x83                                ⁢                                  χ                                      2                    ,                    k                                    2                                ⁢                                  xe2x80x83                                ⁢                …                ⁢                                  xe2x80x83                                ⁢                                  χ                                      K                    ,                    k                                    2                                            ]                        )                    T                                    (        4        )            
using an input signal "khgr"i,k(i=1,2, . . . , K) for the i-th. The calculation circuit of number of taps 130 calculates the number of taps of each adaptive filter every U coefficient adaptations of an adaptive filter using a norm             c      _              i      ,      k        T    ⁢      xe2x80x83    ⁢            c      _              i      ,      k      
of the subband tail coefficient and an input signal "khgr"i,k, where U represents a positive integer. The number of taps Ni,mU at time (mxe2x88x921)UT of the i-th subband adaptive filter is given by the following expression using the number of taps Ni,(mxe2x88x921)U at time (mxe2x88x921)UT.
N1,mU=Ni,(mxe2x88x921)Uxe2x88x92R(mxe2x88x921)Uxc2x7(1xe2x88x92"PHgr"i,mU)xe2x80x83xe2x80x83(5)
                              Φ                      i            ,            mU                          =                  INT          ⁢                      xe2x80x83                    [                      K            xc3x97                                                            ∑                                      p                    =                                                                                            (                                                      m                            -                            1                                                    )                                                ⁢                        U                                            +                      1                                                        mU                                ⁢                                  xe2x80x83                                ⁢                                                      χ                                          i                      ,                      p                                                        ⁢                                                            c                      _                                                              i                      ,                      p                                        T                                    ⁢                                      xe2x80x83                                    ⁢                                                            c                      _                                                              i                      ,                      p                                                                                                                    ∑                                      p                    =                                                                                            (                                                      m                            -                            1                                                    )                                                ⁢                        U                                            +                      1                                                        mU                                ⁢                                  xe2x80x83                                ⁢                                  trace                  ⁢                                      xe2x80x83                                    ⁢                                      {                                                                  v                        p                                            ⁢                                                                        c                          ~                                                p                                                              }                                                                                ]                                    (        6        )            
Here, m is a positive integer, trace {.} is a trace of the matrix, INT [.] represents an operator to take the integer, and R(mxe2x88x921)U represents the number of taps deleted from one subband upon tap coefficient reallocation at one time. Moreover, the number of taps Ni,(mxe2x88x921)U at time (mxe2x88x921)UT is supplied as a signal 101 from adaptive filters 60i(i=1,2, . . . , K) to the calculation circuit of number of taps 130. At this time, the number of taps of each subband also depends upon the subband input signal, therefore, a larger number of taps are assigned to subbands which have a larger signal power. Moreover, by adaptively controlling R(mxe2x88x921)U, making the deleted number of taps upon a tap coefficient reallocation at one time as a time-varying, a small final in tap assignment and fast convergence misadjustment are obtained. In the expression (5), the number of taps which is able to be redistributed is KR(mxe2x88x921)U, as a result of taking the integer by the expression (6), as shown in the expression (7), the number of taps which is able to be redistributed and the redistributed number of taps are not always identical to each other.                                           ∑                          i              =              1                        K                    ⁢                      xe2x80x83                    ⁢                      Φ                          i              ,              mU                                      ≠        K                            (        7        )            
That is to say, in the case where there is an excess or an insufficiency of the number of taps, for example, it is possible to make fine adjustments on the basis of the value of "PHgr"i,mU. A signal 103 which represents the number of taps of each subband obtained by the above evaluations is transported to an adaptive filter 60i(i=1,2, . . . , K).
The redistributed number of taps at one time, R(mxe2x88x921)U, used in the calculation circuit of number of taps 130 is supplied as a signal 106 from the exchange number control circuit 140. The redistributed number of taps RmU is calculated in the exchange number control circuit 140 as follows.
RmU=R(mxe2x88x921)U+R0xc3x97xcex8mUxe2x80x83xe2x80x83(8)
                              θ          mU                =                  {                                                                      +                  1                                                                                                  for                    ⁢                                          xe2x80x83                                        ⁢                                          γ                      mU                                                        =                                                            γ                                                                        (                                                      m                            -                            1                                                    )                                                ⁢                        U                                                              =                                          ⋯                      =                                              γ                                                  mU                          -                          r                                                                                                                                                                                          -                  1                                                                              otherwise                  ⁢                                      xe2x80x83                                                                                }                                    (        9        )            
Where xcex3mU is defined by a subband index i giving max ["PHgr"i,mU]. Here, max [.] represents an operator detecting the maximum value. That is to say, in the case where a subband giving the maximum value of "PHgr"i,mU r times in succession remains to be equal, xcex8mU becomes +1, on the other hand, in the case where a subband giving the maximum value of "PHgr"i,mU does not remain to be equal, xcex8mU becomes xe2x88x921. Moreover, R0 is a predetermined integer. To the interpose number control circuit 140, R(mxe2x88x921)U as a signal 104, "PHgr"i,mU as a signal 105 are supplied and utilized in the calculation of the expression (8) and the expression (9). On the other hand, RmU calculated with the exchange number control circuit 140 is delayed for an U sampling period and becomes R(mxe2x88x921)U. The R(mxe2x88x921)U is feedbacked as a signal 106 to the calculation circuit of number of taps 130 and is used in the calculation of the expression (5).
In FIG. 19, an example of a block diagram of an adaptive filter 60i(i=1,2, . . . , K) is shown. A subband input signal from the decimating circuit 50i is supplied to the input terminal 610, a subband reference signal from the decimating circuit 51i is supplied to the input terminal 620, and a subband error signal which is outputted to the output terminal 630 is transported to the interpolation circuit 70i. Moreover, the number of taps Ni,k from the calculation circuit of number of taps 130 is supplied to the input terminal 640. A signal which is supplied to the input terminal 610 is supplied to a tapped delay line with taps composed of a plurality of delay elements 6111, . . . , 611Nxe2x88x921 generating 1 sampling period delay. An input signal sample supplied to the delay element 6111 is transferred to contiguous delay elements per each clock. The output signal of each delay element 611i(i=1,2, . . . , Nxe2x88x921) Is supplied to the corresponding multiplier 613i+1 by way of the switches 6150, 6151, . . . , 615Nxe2x88x921 respectively, and multiplied by signal supplied from the corresponding coefficient generation circuit 612i+1. Outputs of the multipliers 6131, . . . , 613N are all added by the adder 614, and transported to the subtracter 616. A subband reference signal is supplied to the subtracter 616 by way of the input terminal 620, the output signal of the adder 614 is subtracted and transported as the error signal to the output terminal 630.
The data conversion circuit 641 receives the number of taps Ni,k and generates a control signal for the switches 6150, 6151, 615Nxe2x88x921. For example, although Ni,k is supplied in the form of Ni,k=U (U is a positive integer), the data conversion circuit 641 converts it, and generates a sequence where only the u-th element is 0 and other elements are all 1. Here, the expression Uxe2x89xa6Uxe2x89xa6Nxe2x88x921 holds. The j-th element of this sequence is supplied to the switch 615j. The circuits of switches 6150, 6151, 615Nxe2x88x921 are all opened when 1 is supplied to, and closed when 0 is supplied to. In consequence, the switch 615U, 615U+1, . . . , 615Nxe2x88x921 are all cut down, none of the signals is transported to the multipliers 613U+1, . . . , 613Nxe2x88x921. This is equivalent to an adaptive filter operating with U taps.
Now, suppose LMS algorithm shown in xe2x80x98reference 1xe2x80x99 as a coefficient adaptation algorithm, a block diagram showing a constitution of the coefficient generation circuit 612i(i=1,2, . . . , N) can be represented as FIG. 20. the output of the subtracter 616 of FIG. 19 is supplied to the input terminal 650, the signal from the switch 615ixe2x88x921 of FIG. 19 is supplied to the input terminal 660, and the signal obtained at the output terminal 670 is transported to the multiplier 613i of FIG. 19. The signal from the input terminal 650 and the signal from the input terminal 660 are multiplied in the multiplier 651, the result is supplied to the multiplier 652. In the multiplier 652, the supplied signal is multiplied by a predetermined constant, the product is transported to the adder 653. On the other hand, the addition output of the adder 653 delayed 1 sampling period by way of the delay element 654 is supplied to the adder 653, an accumulation calculations of the value supplied from the multiplier 652 are executed in a loop circuit composed of the delay element 654 and the adder 653. Circulating around the foregoing circuit once corresponds to executing coefficient adaptation once. The output of the adder 653 is transported to the output terminal 670.
When a conventional example described so far is actually realized as a hardware, it is desirable that the difference between the number of taps assigned to each subband immediately after the initiation of the operation of an adaptive filter and that after the convergence is smaller. This difference occurs because the subband charging processing is changed in a portion of chips in the case of realizing it using multiple LSI chips. As a result, it may be difficult to constitute some types of hardware or the some kinds of constraints may be added.
An objective of the present invention is to provide an unknown system identification method and its device performed by a subband adaptive filter of the smaller difference between the number of taps assigned to each subband immediately after the initiation of the operation of an adaptive filter and that after the convergence.
The above-described objective of the present invention is achieved by:
in an unknown system identification method supplying an input signal to an unknown system and simultaneously generating a plurality of subband signals by dividing an input signal into subbands, supplying said plurality of subband signals as input signals to independent adaptive filters, generating a plurality of subband reference signals by dividing an output signal of said unknown system into subbands, making the difference between said plurality of subband reference signals and the output signal of said adaptive filter as a subband error signal, updating coefficients of said adaptive filter using coefficient adaptation algorithm of an adaptive filter so as to minimize said subband error signal, and regarding an updated coefficients as the impulse response of an unknown system,
said unknown system identification method comprising the steps of:
calculating an approximate number of taps of said independent adaptive filters based on coefficient values of said independent adaptive filters, the numbers of taps of said independent adaptive filters, the output signal of said subband unknown system and said plurality of subband input signals,
calculating an optimum number of taps of said independent adaptive filters based on coefficient values of said independent adaptive filters , said plurality of subband input signals and the numbers of taps of said independent adaptive filters,
assigning an initial number of taps to said independent adaptive filters,
assigning said calculated approximate numbers of taps to said independent adaptive filters after a first predetermined time passing, and
assigning said calculated optimum number of taps to said independent adaptive filters after a second predetermined time, and
wherein the increment or decrement of number of taps among said independent adaptive filters at one tap-redistribution is adaptively controlled by continuous changes of the increment or decrement of taps in each adaptive filter.
Also, the above-described objective of the present invention is achieved by:
in an unknown system identification device supplying an input signal of an unknown system to a subband filter bank and generating a plurality of subband signals, supplying said plurality of subband signals as input signals to a plurality of independent adaptive filters, supplying an output signal of said unknown system to a subband filter bank and generating a plurality of subband reference signals, said plurality of subband reference signals and the output signal of said adaptive filter are supplied to a plurality of subtracters and the differences are determined, and regarding an updated coefficient of said adaptive filter using a coefficient adaptation algorithm of an adaptive filter so as to minimize said difference as the impulse response of an unknown system,
said unknown system identification device performed by subband adaptive filters comprising:
a first memory for storing initial numbers of taps with respect to said plurality of adaptive filters;
an approximate tap number calculation circuit for calculating approximate numbers of taps with respect to said plurality of adaptive filters based on coefficient values, input signals and said plurality of subband reference signals from said plurality of adaptive filters and converting said calculated approximate numbers of taps into control signals for number of taps;
a number of taps control circuit for calculating optimum numbers of taps with respect to said plurality of adaptive filters based on coefficient values, the numbers of taps and input signals from said plurality of adaptive filters and converting said calculated optimum numbers of taps into a number of taps control signal;
a selection circuit for receiving said initial number of taps, said approximate numbers of taps and said optimum numbers of taps, selecting one of them and outputting it;
a control circuit for generating a signal for controlling said selection circuit; and a second memory for storing data used in said control circuit.
In the unknown system identification performed by a subband adaptive filter of the present invention, it is characterized in that a plurality of adaptive filters, at first, operate by an initial values of the number of taps, secondly, operate by an approximate number of taps, and then, operate by an optimum number of taps. More particularly, at first, an initial value of the number of taps memorized in the memory circuit 25 of FIG. 1 is selected in the selection circuit 26, secondly, the approximate number of taps calculated in the calculation circuit of approximate number of taps 20 is selected in the selection circuit 26, and then, the optimum number of taps calculated in the tap assignment control circuit 10 is selected in the selection circuit 26, and supplied to adaptive filters 60i(i=1,2, . . . , K).
The number of taps of an adaptive filter in the present invention is composed of two (2) steps of an approximate assignment and an optimum assignment. Therefore, the difference between the number of taps assigned to each subband immediately after the initiation of the operation of an adaptive filter and that after the convergence is smaller.